/**
* created by yang on 25-4-14.
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct student{
    char name[50];
    int age;
    float score;
}Student;

//等价于typedef struct LNode LNode;
//typedef struct LNode *LinkList;这里是一个指向lnode的指针为linklist
typedef struct LNode{
    Student data;
    struct LNode *next;
}LNode,*LinkList;

//不带头结点初始化一个空链表
void InitList(LinkList L);

//带头节点的初始化
void NodeInitList(LinkList L);

int main(){
    LinkList L;//声明一个指向单链表的指针
    NodeInitList(L);
    printf("nihao");
  return 0;
}

//不带头结点
/**
 * 头指针L是一个Linklist指针，指向的是第一个元素
 */
//初始化
void InitList(LinkList L) {
    L = NULL;
}
//不带头结点的按位插入
//后面和带投头结点的几乎一样，除了j=1，但是如果i=1，则需要专门写一段程序处理
void ListInsert(LinkList L,int i,Student e) {
    if (i==1) {
        LNode *s=(LNode *)malloc(sizeof(Student));
        s->data=e;
        s->next=L;
        L=s;
    }
    LNode *p;
    int j = 1;
    p=L;
    while (p!=NULL && j<i-1) {
        p=p->next;
        j++;
    }
    LNode *s=(LNode *)malloc(sizeof(Student));
    s->data=e;
    s->next=p->next;
    p->next=s;

}


//带头结点
/**
 * 头指针L指向的是头结点H
 * H的next指向的是第一个元素
 */
//带头结点初始化
void NodeInitList(LinkList L) {
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
}
//在第i个位置插入，i表示位序
void NodeListInsert(LinkList L,int i,Student e) {
    if (i<1) {
        return;
    }
    LNode *p;//当前指针扫描到了哪个结点
    int j=0;//当前p指向的是第几个结点
    p=L;
    //这个while循环会执行到i-1，也就是说，循环退出时，j=i-1
    while (p!=NULL && j<i-1) {
        p=p->next;
        j++;
    }
    if (p==NULL) {
        return;
    }
    LNode *s=(LNode *)malloc(sizeof(Student));
    s->data=e;
    s->next=p->next;
    p->next=s;
}

//后插入操作
void NodeInsertNextNode(LNode *p,Student e) {
    if (p==NULL) {
        return;
    }
    LNode *s=(LNode *)malloc(sizeof(Student));
    s->data=e;
    s->next=p->next;
    p->next=s;
}

//前插入操作
/**
 * 如果给了第一个指针，那么可以直接遍历到要插入的节点，当然时间复杂度较高
 * 还有一种方法是新建一个结点，直接把他复制了再替换
 */
void InsertPriorNode(LNode *p,Student e) {
    LNode *s=(LNode *)malloc(sizeof(Student));
    s->data = p->data;
    p->data = e;
    s->next = p->next;
    p->next = s;
}

//删除一个结点
void ListDelete(LinkList *L,int i,Student e) {
    LNode *p = L;
    int j=0;
    while (p!=NULL && j<i-1 ) {
        p = p->next;
        j++;
    }

    LNode *s = p->next;
    e = s->data; //这里怎么返回，指针的引用？？
    p->next=s->next;
    free(s);
}

//删除一个指定结点
/**
 * 同前插操作类似，我们无法去访问前面的结点，所以有两种办法
 * 一种是换，一种是便利，如果遇到删除的是最后一个结点，那么只能是遍历
 */
void DeleteNode(LNode *p) {
    LNode *L= p->next;
    p->data = L->data; //如果是最后一个结点，那么next为空有错误，所以只能用遍历
    p->next=L->next;
    free(L);
}

//按位查找
LNode * GetElem(LinkList L,Student e) {
    LNode *p = L->next;
    while (p!=NULL && p->data.age==e.age) {
        p=p->next;
    }
    return p;
}
//按值查找
LNode * LocateElem(LinkList L,int i) {
    int j=0;
    LNode *p = L;
    while (p!=NULL && j<i) {
        p=p->next;
        j++;
    }
    return p;
}

//求表长
int Length(LinkList L) {
    int len=0;
    LNode *p = L;
    while (L->next!=NULL) {
        p = p->next;
        len++;
    }
    return len;
}

//正向建立一个单链表，尾插法
LinkList List_TailInsert(LinkList *L) {
    int x;
    L = (LNode *)malloc(sizeof(Student));//建立头结点
    LNode *s,*r=L; //r为表尾指针，s为中间新开的结点指针
    printf("请输入结点值");
    scanf("&d",&x);//输入结点的值

    while (x!=520) { //这个520值是用来结束循环的
        s = (LNode *)malloc(sizeof(Student));
        s->data.age=x;  //赋值
        r->next = s;   //前一个结点next指向新开的结点
        r=s;      //更改前一个结点为当前结点
        scanf("%d",&x);
    }
    r->next=NULL;
    return L;
}

//建立头插法
//重要应用，链表的逆置
LinkList List_HeadInsert(LinkList L) {
    int x;
    L=(LNode *)malloc(sizeof(Student));//创建头结点
    L->next=NULL;  //这里一定要为空，可能有脏数据
    LNode *s = L;
    printf("请输入要插入的数据");
    scanf("%d",&x);

    while (x!=520) {
        s =(LNode *)malloc(sizeof(Student));
        s->next=L->next;
        s->data.age=x;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

//链表的逆置



/**
 * 循环链表，结构体定义和单链表的一样
 */

//初始化一个循环链表
void InitCircleList(LinkList L) {
    L = (LNode *)malloc(sizeof(Student));
    if (L==NULL) {
        return;
    }
    L->next =L;
    printf("init CircleList success");
}

//判断结点p是否为循环单链表的表尾结点
void isTail(LinkList L,LNode *p) {
    if (p->next==L) {
        printf("is tail");
    }else {
        printf("no tail");
    }
}


